//  https://leetcode-cn.com/problems/search-insert-position
//  SearchInsertPosition.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/29.
//  Copyright © 2019 XFB. All rights reserved.
//  搜索插入位置【 时间复杂度O(N)   空间复杂度O(1) 】

import Foundation

class SearchInsertPosition {
    
    /**
     给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     你可以假设数组中无重复元素。
     示例 1:
     输入: [1,3,5,6], 5
     输出: 2
     
     示例 2:
     输入: [1,3,5,6], 2
     输出: 1
     
     示例 3:
     输入: [1,3,5,6], 7
     输出: 4
     
     示例 4:
     输入: [1,3,5,6], 0
     输出: 0
     
     遍历数组
     如果目标数target小于等于 nums[i], 则返回下标 i
     循环能走完，则目标数target 比数组最后一个数还要大，返回数组长度 length + 1
     二分法查找：数据线排好顺序 设置查找数组区间为 array[low, high]
     */

    /// 时间复杂度 O(N) 空间复杂度 O(1)
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        
        guard nums.count > 0 else {
            return 0
        }
        
        /// 左 中 右 索引
        var left = 0
        var middle = 0
        var right = nums.count - 1
        
        /// left+1 考虑 middle
        while left + 1 < right {
            
            /// 取中间点
            middle = (right - left) / 2 + left
            
            if nums[middle] == target {
                return middle
            } else if nums[middle] < target {
                left = middle
            } else if nums[middle] > target {
                right = middle
            }
        }
        
        if nums[right] < target {
            return right + 1
        }
        
        if nums[left] >= target {
            return left
        }
        
        return right
    }
    
    
    
    /// 我丢
    func searchInsert1(_ nums: [Int], _ target: Int) -> Int {
        
        guard nums.count > 0 else {
            return 0
        }
        
        for i in 0 ..< nums.count {
            if nums[i] >= target {
                return i
            }
        }
        return nums.count
    }
    
    /// 元素 1 3 5 6
    /// 位置 0 1 2 3
    /// target = 2、4
    /// middle = (0 + 3)/2 = 1
    /// nums[middle] = nums[1] = 3
    /// nums[middle - 1] = 1
    /// nums[middle + 1] = 5
    /// 1 < 3 < 5
    /// nums[middle - 1]  <  nums[middle]  <  nums[middle + 1]
    
    /**
     target == nums[middle]         index = middle
     target <  nums[middle] 且 middle == 0 或 target > nums[middle - 1]
     target >  nums[middle] 且 middle == nums.count - 1 或 target < nums[middle + 1]
     
     */
    func searchInsert2(_ nums: [Int], _ target: Int) -> Int {
       
        var index = -1
        var start = 0
        var end = nums.count - 1
        
        while index == -1 {
            
            let middle = (end - start) / 2 + start
            if nums[middle] == target {
                index = middle
            } else if nums[middle] < target {
                if middle == nums.count - 1 || nums[middle + 1] > target {
                    /// 重点
                    index = middle + 1
                }
                start = middle + 1
            } else if nums[middle] > target {
                if middle == 0 || nums[middle - 1] < target {
                    index = middle
                }
                end = middle - 1
             }
        }
        return index
    }
}
